from typing import List


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def dfs(begin, length, path):
            if length == k:
                res.append(path[:])
                return
            # Now length < k
            for i in range(begin, n+1):
                path.append(i)
                dfs(i+1, length+1, path)
                path.pop()
        
        dfs(begin=1, length=0, path=[])
        return res
